{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 迪杰斯特拉简单实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def dijkstra(matrix, source):\n",
    "    \"\"\"迪杰斯特拉算法实现\n",
    "    Args:\n",
    "        matrix (_type_): 用邻接矩阵表示带权图\n",
    "        source (_type_): 起点\n",
    "\n",
    "    Returns:\n",
    "        _type_: 最短路径的节点集合，最短路径的节点的最短距离，每个节点到起点的最短路径\n",
    "    \"\"\"\n",
    "    INF = float('inf')\n",
    "    n = len(matrix)\n",
    "    m = len(matrix[0])\n",
    "    assert n == m, \"Error, please examine matrix dim\"\n",
    "    assert source < n, \"Error, start point should be in the range!\"\n",
    "    S = [source]        # 已找到最短路径的节点集合\n",
    "    U = [v for v in range(n) if v not in S]  # 记录还未确定最短路径的节点集合\n",
    "    distance = [INF] * n          # source到已找到最短路径的节点的最短距离\n",
    "    distance[source] = 0  # 起点到自己的距离\n",
    "    path_optimal = [[]]*n           # source到其他节点的最短路径\n",
    "    path_optimal[source] = [source]\n",
    "    while len(S) < n:   # 当已找到最短路径的节点小于n时\n",
    "        min_value = INF\n",
    "        col = -1\n",
    "        row = -1\n",
    "        for s in S:     # 以已找到最短路径的节点所在行为搜索对象\n",
    "            for u in U:   # 从U中搜索尚未记录的节点\n",
    "                if matrix[s][u] + distance[s] < min_value:  # 找出最小值\n",
    "                    # 在某行找到最小值要加上source到该行的最短路径\n",
    "                    min_value = matrix[s][u] + distance[s]\n",
    "                    row = s         # 记录所在行列\n",
    "                    col = u\n",
    "        if col == -1 or row == -1:  # 若没找出最小值且节点还未找完，说明图中存在不连通的节点\n",
    "            break\n",
    "        S.append(col)  # 在S中添加已找到的节点\n",
    "        U.remove(col)  # 从U中移除已找到的节点\n",
    "        distance[col] = min_value # source到该节点的最短距离即为min_value\n",
    "        path_optimal[col] = path_optimal[row][:]    # 复制source到已找到节点的上一节点的路径\n",
    "        path_optimal[col].append(col)       # 再其后添加已找到节点即为sorcer到该节点的最短路径\n",
    "    return S, distance, path_optimal\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "假设有如下路径，起点是D。A—G分别用0—6表示\n",
    "\n",
    "\n",
    "![在这里插入图片描述](https://img-blog.csdnimg.cn/53211efebe97434e992dea17b3f76b16.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def main():\n",
    "    INF = float('inf')\n",
    "    # 使用邻接矩阵存储图\n",
    "    # A B C D E F G\n",
    "    matrix = [[0, 12, INF, INF, INF, 16, 14],\n",
    "              [12, 0, 10, INF, INF, 7, INF],\n",
    "              [INF, 10, 0, 3, 5, 6, INF],\n",
    "              [INF, INF, 3, 0, 4, INF, INF],\n",
    "              [INF, INF, 5, 4, 0, 2, 8],\n",
    "              [16, 7, 6, INF, 2, 0, 9],\n",
    "              [14, INF, INF, INF, 8, 9, 0]]\n",
    "    source = 3\n",
    "    S, distance, path_optimal = dijkstra(matrix, source)\n",
    "    print('S:')\n",
    "    print(S)\n",
    "    print('distance:')\n",
    "    print(distance)\n",
    "    print('path_optimal:')\n",
    "    for i, p in enumerate(path_optimal):\n",
    "        print(source,\"->\",i, \"最短路径: \", p)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "S:\n",
      "[3, 2, 4, 5, 6, 1, 0]\n",
      "distance:\n",
      "[22, 13, 3, 0, 4, 6, 12]\n",
      "path_optimal:\n",
      "3 -> 0 最短路径:  [3, 4, 5, 0]\n",
      "3 -> 1 最短路径:  [3, 2, 1]\n",
      "3 -> 2 最短路径:  [3, 2]\n",
      "3 -> 3 最短路径:  [3]\n",
      "3 -> 4 最短路径:  [3, 4]\n",
      "3 -> 5 最短路径:  [3, 4, 5]\n",
      "3 -> 6 最短路径:  [3, 4, 6]\n"
     ]
    }
   ],
   "source": [
    "main()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "0c7484b3574347463e16b31029466871583b0d4e5c4ad861e8848f2d3746b4de"
  },
  "kernelspec": {
   "display_name": "Python 3.8.12 ('gobigger')",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.12"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
